package com.example.leetcode;

/**
 * 动态规划
 * 矩阵不可变
 * 递归条件为前缀和
 */
public class Demo0304 {

    public static void main(String[] args) {
        int[][] sum=new int[1][1];
        System.out.println(sum[1][1]);
    }

    int[][] sums;

//    public Demo0304(int[][] matrix) {
//        int m = matrix.length;
//        if (m >0){
//            int n=matrix[0].length;
//            sums=new int[m][n];
//            for (int i = 0; i < m; i++) {
//                for (int j = 0; j <n ; j++) {
//                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
//                }
//            }
//        }
//    }
//
//    public int sumRegion(int row1, int col1, int row2, int col2) {
//        return sums[row2+1][col2+1]-sums[row1][col2+1]-sums[row2+1][col1]+sums[row1][col1];
//    }

    public Demo0304(int[][] matrix) {
        int m = matrix.length;
        if (m >0){
            int n=matrix[0].length;
            sums=new int[m+1][n+1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j <n ; j++) {
                    sums[i+1][j+1]=sums[i+1][j]+sums[i][j+1]-sums[i][j]+matrix[i][j];
                }
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2+1][col2+1]-sums[row1][col2+1]-sums[row2+1][col1]+sums[row1][col1];
    }
}
